package offer2

/*
*
原题链接:
https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
*/
func maxSales(sales []int) int {
	if len(sales) == 0 {
		return 0
	} //判空
	n := len(sales)      // 获取数组的长度
	dp := make([]int, n) // dp[i] 表示以第 i 个元素结尾的最大子数组的和

	dp[0] = sales[0] // dp[0] 表示以第 0 个元素结尾的最大子数组的和   初始化 dp[0]
	maxNum := dp[0]  // 变量 maxNum 表示数组 dp 中最大的那个值, 即 maxNum 表示最大的连续字段和

	// 从 1 开始遍历 sales
	for i := 1; i < n; i++ {
		if dp[i-1] > 0 { // 在遍历的过程中，去获取以第 i 个元素结尾的最大子数组的和    如果以 sales[i-1] 为结尾的最大字段和为正数, 那么以第 i 个元素结尾的最大子数组的和就是自己本身加上以 sales[i-1] 结尾的最大字段和
			dp[i] = sales[i] + dp[i-1]
		} else {
			dp[i] = sales[i] // 否则 dp[i-1] 不是正数，为负数或者0, 不加前一位的值会更大, 直接赋值sales[i]的值即可
		}

		if maxNum < dp[i] { // 在更新 dp[i] 的过程中，更新 maxNum 的值
			maxNum = dp[i]
		}
	}

	// 最后返回 maxNum
	return maxNum

}
